// package dp dynamic programming 动态规划
package dp

// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn854d/
// 爬楼梯的方法数统计
// 时间复杂度: O(n)
func ClimbStairs(n int) int {
	if 1 == n {
		return 1
	}
	if 2 == n {
		return 2
	}
	climbMethodArr := make([]int, n+1)
	climbMethodArr[1], climbMethodArr[2] = 1, 2
	for index := 3; index <= n; index++ {
		climbMethodArr[index] = climbMethodArr[index-1] + climbMethodArr[index-2]
	}
	return climbMethodArr[n]
}
